#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// Dijkstra算法模版（洛谷）
// 静态空间实现 : 链式前向星 + 反向索引堆
// 测试链接 : https://www.luogu.com.cn/problem/P4779

const int MAXN = 100001;
const int MAXM = 200001;
const int INF = 0x3f3f3f3f;
// 链式前向星
int head[MAXN];
int next[MAXM];
int to[MAXM];
int weight[MAXM];
int cnt;

int dist[MAXN];
int heap[MAXN];
// where[i] = -1：节点 i 没有进过堆
// where[i] = -2：节点 i 从堆中弹出过
// where[i] >= 0：节点 i 在堆中的位置
int where[MAXN]; // 记录节点在堆中的位置
int heapSize; // 堆中的元素个数

// 题目输入的参数
int n, m, s;    


void build(int n)
{
    cnt = 1;
    heapSize = 0;
    // fill(head + 1, head + n + 1, 0);
    fill(where + 1, where + n + 1, -1);
    fill(dist + 1, dist + n + 1, INF);
}

// 链式前向星加边
void addEdge(int u, int v, int w)
{
    ::next[cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt++;
}

void swap(int i, int j)
{
    int tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
    where[heap[i]] = i;
    where[heap[j]] = j;
}

void heapInsert(int i)
{
    while(dist[heap[i]] < dist[heap[(i - 1) / 2]])
    {
        ::swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

void addOrUpdateOrIgnore(int v, int c)
{
    if(where[v] == -1)
    {
        heap[heapSize] = v;
        where[v] = heapSize++;
        dist[v] = c;
        heapInsert(where[v]);
    }
    else if(where[v] >= 0)
    {
        dist[v] = min(dist[v], c);
        heapInsert(where[v]);
    }
}

void heapify(int i)
{
    int l = 2 * i + 1;
    while(l < heapSize)
    {
        int best = l + 1 < heapSize && dist[heap[l + 1]] < dist[heap[l]] ? l + 1 : l;
        best = dist[heap[best]] < dist[heap[i]] ? best : i;
        if(best == i) break;
        ::swap(best, i);
        i = best;
        l = 2 * i + 1;
    }
}

int pop()
{
    int ret = heap[0];
    ::swap(0, --heapSize);
    heapify(0);
    where[ret] = -2;
    return ret;
}

bool isEmpty()
{
    return heapSize == 0;
}

void dijkstra()
{
    addOrUpdateOrIgnore(s, 0);
    while(!isEmpty())
    {
        int u = pop();
        for(int ei = head[u]; ei > 0; ei = ::next[ei])
        {
            addOrUpdateOrIgnore(to[ei], dist[u] + weight[ei]);
        }
    }
}


int main()
{
    cin >> n >> m >> s;
    build(n);
    int u, v, w;
    for(int i = 0; i < m; ++i)
    {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    dijkstra();
    cout << dist[1];
    for(int i = 2; i <= n; ++i)
    {
        cout << " " << dist[i];
    }
    cout << endl;

    return 0;
}